fft[離散傅氏變換的快速算法]

FFT（Fast Fourier Transformation）是離散傅氏變換（DFT）的快速算法。即為快速傅氏變換。它是根據離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。

基本信息

• 中文名：離散傅氏變換的快速算法
• 英文名：Fast Fourier Transformation

• 表達式：FFT
• 套用學科：數學
• 適用領域範圍：數位訊號處理

算法

FFT是一種DFT的高效算法，稱為快速傅立葉變換（fast Fourier transform），它根據離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。FFT算法可分為按時間抽取算法和按頻率抽取算法，先簡要介紹FFT的基本原理。從DFT運算開始，說明FFT的基本原理。

DFT的運算為：

fft[離散傅氏變換的快速算法]

fft[離散傅氏變換的快速算法]

式中

fft[離散傅氏變換的快速算法]

fft[離散傅氏變換的快速算法]

由這種方法計算DFT對於 的每個K值，需要進行4N次實數相乘和（4N-2）次相加，對於N個k值，共需4N*N次實數相乘和（4N-2)*N次實數相加。改進DFT算法，減小它的運算量，利用DFT中 的周期性和對稱性，使整個DFT的計算變成一系列疊代運算，可大幅度提高運算過程和運算量，這就是FFT的基本思想。

FFT算法圖(Butterfly算法)

FFT對傅氏變換的理論並沒有新的發現，但是對於在計算機系統或者說數字系統中套用離散傅立葉變換，可以說是進了一大步。

設x(n)為N項的複數序列，由DFT變換，任一X（m）的計算都需要N次複數乘法和N-1次複數加法，而一次複數乘法等於四次實數乘法和兩次實數加法，一次複數加法等於兩次實數加法，即使把一次複數乘法和一次複數加法定義成一次“運算”（四次實數乘法和四次實數加法），那么求出N項複數序列的X（m）,即N點DFT變換大約就需要N^2次運算。當N=1024點甚至更多的時候，需要N =1048576次運算，在FFT中，利用WN的周期性和對稱性，把一個N項序列（設N=2k,k為正整數），分為兩個N/2項的子序列，每個N/2點DFT變換需要（N/2） 次運算，再用N次運算把兩個N/2點的DFT變換組合成一個N點的DFT變換。這樣變換以後，總的運算次數就變成N+2*（N/2)^2=N+（N^2）/2。繼續上面的例子，N=1024時，總的運算次數就變成了525312次，節省了大約50%的運算量。而如果我們將這種“一分為二”的思想不斷進行下去，直到分成兩兩一組的DFT運算單元，那么N點的DFT變換就只需要N/2log2N次的運算，N在1024點時，運算量僅有5120次，是先前的直接算法的近1/200，點數越多，運算量的節約就越大，這就是FFT的優越性。

公式

fft[離散傅氏變換的快速算法]

其中

fft[離散傅氏變換的快速算法]

源碼含義

在C環境下的源碼

源碼（1）：

註：親測，這個版本無法運行，作者刪改了重要內容  請參考源碼（2）

源碼（2）

ps:可以運行的

在C++環境下的源碼

在Matlab環境下的源碼

function X=myfft(x)

N=length(x);

if N==1

X=x;

return;

end

%myfft函式 用遞歸實現

t=log2(N);

t1=floor(t);

t2=ceil(t);

if t1~=t2; %若x的長度N不為2的整數次冪，則補0至最接近的2的整數次冪

x=[x zeros(1,2^t2-N)];

N=2^t2;

end

w0=exp(-1i*2*pi/N);

X=zeros(1,N);

n=1:N/2;

xo(n)=x(2*n-1);

xe(n)=x(2*n);

XO=myfft(xo); %遞歸調用

XE=myfft(xe);

for n=1:N/2

X(n)=XO(n)+XE(n)*(w0^(n-1));

X(n+N/2)=XO(n)-XE(n)*(w0^(n-1));

end

使用方法

一.調用方法

X=FFT(x)；
X=FFT(x，N)； 

x=IFFT(X);
x=IFFT(X,N)
用MATLAB進行譜分析時注意：
（1）函式FFT返回值的數據結構具有對稱性。
例：
N=8;
n=0:N-1;
xn=[4 3 2 6 7 8 9 0];
Xk=fft(xn)
→
Xk =

39.0000 -10.7782 + 6.2929i 0 - 5.0000i 4.7782 - 7.7071i 5.0000 4.7782 + 7.7071i 0 + 5.0000i -10.7782 - 6.2929i
Xk與xn的維數相同，共有8個元素。Xk的第一個數對應於直流分量，即頻率值為0。
（2）做FFT分析時，幅值大小與FFT選擇的點數有關，但不影響分析結果。在IFFT時已經做了處理。要得到真實的振幅值的大小，只要將得到的變換後結果乘以2除以N即可。
二.FFT套用舉例

例1：x=0.5*sin(2*pi*15*t)+2*sin(2*pi*40*t)。採樣頻率fs=100Hz，分別繪製N=128、1024點幅頻圖。
clf;
fs=100;N=128; %採樣頻率和數據點數
n=0:N-1;t=n/fs; %時間序列
x=0.5*sin(2*pi*15*t)+2*sin(2*pi*40*t); %信號
y=fft(x,N); %對信號進行快速Fourier變換
mag=abs(y); %求得Fourier變換後的振幅
f=n*fs/N; %頻率序列
subplot(2,2,1),plot(f,mag); %繪出隨頻率變化的振幅
xlabel('頻率/Hz');
ylabel('振幅');title('N=128');grid on;
subplot(2,2,2),plot(f(1:N/2),mag(1:N/2)); %繪出Nyquist頻率之前隨頻率變化的振幅
xlabel('頻率/Hz');
ylabel('振幅');title('N=128');grid on;
%對信號採樣數據為1024點的處理
fs=100;N=1024;n=0:N-1;t=n/fs;
x=0.5*sin(2*pi*15*t)+2*sin(2*pi*40*t); %信號
y=fft(x,N); %對信號進行快速Fourier變換
mag=abs(y); %求取Fourier變換的振幅
f=n*fs/N;
subplot(2,2,3),plot(f,mag); %繪出隨頻率變化的振幅
xlabel('頻率/Hz');
ylabel('振幅');title('N=1024');grid on;
subplot(2,2,4)
plot(f(1:N/2),mag(1:N/2)); %繪出Nyquist頻率之前隨頻率變化的振幅
xlabel('頻率/Hz');
ylabel('振幅');title('N=1024');grid on;
運行結果：

fs=100Hz，Nyquist頻率為fs/2=50Hz。整個頻譜圖是以Nyquist頻率為對稱軸的。並且可以明顯識別出信號中含有兩種頻率成分：15Hz和40Hz。由此可以知道FFT變換數據的對稱性。因此用FFT對信號做譜分析，只需考察0~Nyquist頻率範圍內的幅頻特性。若沒有給出採樣頻率和採樣間隔，則分析通常對歸一化頻率0~1進行。另外，振幅的大小與所用採樣點數有關，採用128點和1024點的相同頻率的振幅是有不同的表現值，但在同一幅圖中，40Hz與15Hz振動幅值之比均為4：1，與真實振幅0.5：2是一致的。為了與真實振幅對應，需要將變換後結果乘以2除以N。
例2：x=0.5*sin(2*pi*15*t)+2*sin(2*pi*40*t),fs=100Hz,繪製：
（1）數據個數N=32，FFT所用的採樣點數NFFT=32；
（2）N=32，NFFT=128；
（3）N=136，NFFT=128；
（4）N=136，NFFT=512。
clf;fs=100; %採樣頻率
Ndata=32; %數據長度
N=32; %FFT的數據長度
n=0:Ndata-1;t=n/fs; %數據對應的時間序列
x=0.5*sin(2*pi*15*t)+2*sin(2*pi*40*t); %時間域信號
y=fft(x,N); %信號的Fourier變換
mag=abs(y); %求取振幅
f=(0:N-1)*fs/N; %真實頻率
subplot(2,2,1),plot(f(1:N/2),mag(1:N/2)*2/N); %繪出Nyquist頻率之前的振幅
xlabel('頻率/Hz');ylabel('振幅');
title('Ndata=32 Nfft=32');grid on;

Ndata=32; %數據個數
N=128; %FFT採用的數據長度
n=0:Ndata-1;t=n/fs; %時間序列
x=0.5*sin(2*pi*15*t)+2*sin(2*pi*40*t);
y=fft(x,N);
mag=abs(y);
f=(0:N-1)*fs/N; %真實頻率
subplot(2,2,2),plot(f(1:N/2),mag(1:N/2)*2/N); %繪出Nyquist頻率之前的振幅
xlabel('頻率/Hz');ylabel('振幅');
title('Ndata=32 Nfft=128');grid on;

Ndata=136; %數據個數
N=128; %FFT採用的數據個數
n=0:Ndata-1;t=n/fs; %時間序列
x=0.5*sin(2*pi*15*t)+2*sin(2*pi*40*t);
y=fft(x,N);
mag=abs(y);
f=(0:N-1)*fs/N; %真實頻率
subplot(2,2,3),plot(f(1:N/2),mag(1:N/2)*2/N); %繪出Nyquist頻率之前的振幅
xlabel('頻率/Hz');ylabel('振幅');
title('Ndata=136 Nfft=128');grid on;

Ndata=136; %數據個數
N=512; %FFT所用的數據個數
n=0:Ndata-1;t=n/fs; %時間序列
x=0.5*sin(2*pi*15*t)+2*sin(2*pi*40*t);
y=fft(x,N);
mag=abs(y);
f=(0:N-1)*fs/N; %真實頻率
subplot(2,2,4),plot(f(1:N/2),mag(1:N/2)*2/N); %繪出Nyquist頻率之前的振幅
xlabel('頻率/Hz');ylabel('振幅');
title('Ndata=136 Nfft=512');grid on;

結論：
（1）當數據個數和FFT採用的數據個數均為32時，頻率解析度較低，但沒有由於添零而導致的其他頻率成分。
（2）由於在時間域內信號加零，致使振幅譜中出現很多其他成分，這是加零造成的。其振幅由於加了多個零而明顯減小。
（3）FFT程式將數據截斷，這時解析度較高。
（4）也是在數據的末尾補零，但由於含有信號的數據個數足夠多，FFT振幅譜也基本不受影響。
對信號進行頻譜分析時，數據樣本應有足夠的長度，一般FFT程式中所用數據點數與原含有信號數據點數相同，這樣的頻譜圖具有較高的質量，可減小因補零或截斷而產生的影響。

例3：x=cos(2*pi*0.24*n)+cos(2*pi*0.26*n)

（1）數據點過少，幾乎無法看出有關信號頻譜的詳細信息；
（2）中間的圖是將x(n)補90個零，幅度頻譜的數據相當密，稱為高密度頻譜圖。但從圖中很難看出信號的頻譜成分。
（3）信號的有效數據很長，可以清楚地看出信號的頻率成分，一個是0.24Hz，一個是0.26Hz，稱為高解析度頻譜。
可見，採樣數據過少，運用FFT變換不能分辨出其中的頻率成分。添加零後可增加頻譜中的數據個數，譜的密度增高了，但仍不能分辨其中的頻率成分，即譜的解析度沒有提高。只有數據點數足夠多時才能分辨其中的頻率成分。